


<!DOCTYPE html>
<html id="htmlId">
<head>
  <title>Coverage Report > TreeNode</title>
  <style type="text/css">
    @import "../../css/coverage.css";
    @import "../../css/highlight-idea.css";
  </style>
  <script type="text/javascript" src="../../js/highlight.pack.js"></script>
</head>

<body>
<div class="content">
<div class="breadCrumbs">
Current scope:     <a href="../../index.html">all classes</a>
    <span class="separator">|</span>
    <a href="../index.html">net.mooctest</a>
</div>

<h1>Coverage Summary for Class: TreeNode (net.mooctest)</h1>

<table class="coverageStats">

<tr>
  <th class="name">Class</th>
<th class="coverageStat 
">
  Method, %
</th>
<th class="coverageStat 
">
  Line, %
</th>
</tr>
<tr>
  <td class="name">TreeNode</td>
<td class="coverageStat">
  <span class="percent">
    37.8%
  </span>
  <span class="absValue">
    (14/37)
  </span>
</td>
<td class="coverageStat">
  <span class="percent">
    19.4%
  </span>
  <span class="absValue">
    (41/211)
  </span>
</td>
</tr>
  <tr>
    <td class="name">TreeNode$1</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/3)
  </span>
</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/5)
  </span>
</td>
  </tr>
  <tr>
    <td class="name">TreeNode$2</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/3)
  </span>
</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/5)
  </span>
</td>
  </tr>
  <tr>
    <td class="name">TreeNode$3</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/3)
  </span>
</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/3)
  </span>
</td>
  </tr>
  <tr>
    <td class="name">TreeNode$4</td>
<td class="coverageStat">
  <span class="percent">
    100%
  </span>
  <span class="absValue">
    (3/3)
  </span>
</td>
<td class="coverageStat">
  <span class="percent">
    100%
  </span>
  <span class="absValue">
    (9/9)
  </span>
</td>
  </tr>
  <tr>
    <td class="name">TreeNode$5</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/3)
  </span>
</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/3)
  </span>
</td>
  </tr>
  <tr>
    <td class="name">TreeNode$TreeNodeIterator</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/8)
  </span>
</td>
<td class="coverageStat">
  <span class="percent">
    0%
  </span>
  <span class="absValue">
    (0/56)
  </span>
</td>
  </tr>
<tr>
  <td class="name"><strong>Total</strong></td>
<td class="coverageStat">
  <span class="percent">
    28.3%
  </span>
  <span class="absValue">
    (17/60)
  </span>
</td>
<td class="coverageStat">
  <span class="percent">
    17.1%
  </span>
  <span class="absValue">
    (50/292)
  </span>
</td>
</tr>
</table>

<br/>
<br/>


<pre>
<div class="sourceCode" id="sourceCode"><i class="no-highlight">1</i>&nbsp;package net.mooctest;
<i class="no-highlight">2</i>&nbsp;
<i class="no-highlight">3</i>&nbsp;import java.io.Serializable;
<i class="no-highlight">4</i>&nbsp;import java.lang.reflect.Array;
<i class="no-highlight">5</i>&nbsp;import java.util.*;
<i class="no-highlight">6</i>&nbsp;import java.util.concurrent.atomic.AtomicLong;
<i class="no-highlight">7</i>&nbsp;
<i class="no-highlight">8</i>&nbsp;/**
<i class="no-highlight">9</i>&nbsp; * This interface represents the basic tree data structure
<i class="no-highlight">10</i>&nbsp; * &lt;h1&gt;Definition&lt;/h1&gt;
<i class="no-highlight">11</i>&nbsp; * A tree data structure can be defined recursively (locally) as a collection of nodes
<i class="no-highlight">12</i>&nbsp; * (starting at a root node), where each node is a data structure consisting of a value,
<i class="no-highlight">13</i>&nbsp; * together with a list of references to nodes (the children), with the constraints that
<i class="no-highlight">14</i>&nbsp; * no reference is duplicated, and none points to the root
<i class="no-highlight">15</i>&nbsp; * &lt;p&gt;
<i class="no-highlight">16</i>&nbsp; * A tree is a (possibly non-linear) data structure made up of nodes or vertices and edges
<i class="no-highlight">17</i>&nbsp; * without having any cycle. The tree with no nodes is called the &lt;b&gt;null&lt;/b&gt; or
<i class="no-highlight">18</i>&nbsp; * &lt;b&gt;empty&lt;/b&gt; tree. A tree that is not empty consists of a root node and potentially many
<i class="no-highlight">19</i>&nbsp; * levels of additional nodes that form a hierarchy
<i class="no-highlight">20</i>&nbsp; * &lt;h1&gt;Terminology&lt;/h1&gt;
<i class="no-highlight">21</i>&nbsp; * &lt;ul&gt;
<i class="no-highlight">22</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Node&lt;/b&gt; - a single point of a tree&lt;/li&gt;
<i class="no-highlight">23</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Edge&lt;/b&gt; - line, which connects two distinct nodes&lt;/li&gt;
<i class="no-highlight">24</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Root&lt;/b&gt; - top node of the tree, which has no parent&lt;/li&gt;
<i class="no-highlight">25</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Parent&lt;/b&gt; - a node, other than the root, which is connected to other successor
<i class="no-highlight">26</i>&nbsp; *                         nodes&lt;/li&gt;
<i class="no-highlight">27</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Child&lt;/b&gt; - a node, other than the root, which is connected to predecessor&lt;/li&gt;
<i class="no-highlight">28</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Leaf&lt;/b&gt; - a node without children&lt;/li&gt;
<i class="no-highlight">29</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Path&lt;/b&gt; - a sequence of nodes and edges connecting a node with a
<i class="no-highlight">30</i>&nbsp; *                       descendant&lt;/li&gt;
<i class="no-highlight">31</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Path Length&lt;/b&gt; - number of nodes in the path - 1&lt;/li&gt;
<i class="no-highlight">32</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Ancestor&lt;/b&gt; - the top parent node of the path&lt;/li&gt;
<i class="no-highlight">33</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Descendant&lt;/b&gt; - the bottom child node of the path&lt;/li&gt;
<i class="no-highlight">34</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Siblings&lt;/b&gt; - nodes, which have the same parent&lt;/li&gt;
<i class="no-highlight">35</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Subtree&lt;/b&gt; - a node in a tree with all of its proper descendants, if any&lt;/li&gt;
<i class="no-highlight">36</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Node Height&lt;/b&gt; - the number of edges on the longest downward path between that
<i class="no-highlight">37</i>&nbsp; *                              node and a leaf&lt;/li&gt;
<i class="no-highlight">38</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Tree Height&lt;/b&gt; - the number of edges on the longest downward path between the
<i class="no-highlight">39</i>&nbsp; *                              root and a leaf (root height)&lt;/li&gt;
<i class="no-highlight">40</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Depth (Level)&lt;/b&gt; - the path length between the root and the current node&lt;/li&gt;
<i class="no-highlight">41</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Ordered Tree&lt;/b&gt; - tree in which nodes has the children ordered&lt;/li&gt;
<i class="no-highlight">42</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Labeled Tree&lt;/b&gt; - tree in which a label or value is associated with each node
<i class="no-highlight">43</i>&nbsp; *                               of the tree&lt;/li&gt;
<i class="no-highlight">44</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Expression Tree&lt;/b&gt; - tree which specifies the association of an expression?s
<i class="no-highlight">45</i>&nbsp; *                                  operands and its operators in a uniform way, regardless
<i class="no-highlight">46</i>&nbsp; *                                  of whether the association is required by the placement
<i class="no-highlight">47</i>&nbsp; *                                  of parentheses in the expression or by the precedence and
<i class="no-highlight">48</i>&nbsp; *                                  associativity rules for the operators involved&lt;/li&gt;
<i class="no-highlight">49</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Branching Factor&lt;/b&gt; - maximum number of children a node can have&lt;/li&gt;
<i class="no-highlight">50</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Pre order&lt;/b&gt; - a form of tree traversal, where the action is called firstly on
<i class="no-highlight">51</i>&nbsp; *                           the current node, and then the pre order function is called again
<i class="no-highlight">52</i>&nbsp; *                           recursively on each of the subtree from left to right&lt;/li&gt;
<i class="no-highlight">53</i>&nbsp; *     &lt;li&gt;&lt;b&gt;Post order&lt;/b&gt; - a form of tree traversal, where the post order function is called
<i class="no-highlight">54</i>&nbsp; *                            recursively on each subtree from left to right and then the
<i class="no-highlight">55</i>&nbsp; *                            action is called&lt;/li&gt;
<i class="no-highlight">56</i>&nbsp; * &lt;/ul&gt;
<i class="no-highlight">57</i>&nbsp; *
<i class="no-highlight">58</i>&nbsp; * @author shell
<i class="no-highlight">59</i>&nbsp; * @version 1.0.0
<i class="no-highlight">60</i>&nbsp; * @since 1.0.0
<i class="no-highlight">61</i>&nbsp; */
<i class="no-highlight">62</i>&nbsp;public abstract class TreeNode&lt;T&gt; implements Iterable&lt;TreeNode&lt;T&gt;&gt;, Serializable, Cloneable {
<i class="no-highlight">63</i>&nbsp;
<i class="no-highlight">64</i>&nbsp;	/**
<i class="no-highlight">65</i>&nbsp;	 * Identifier generator, used to get a unique id for each created tree node
<i class="no-highlight">66</i>&nbsp;	 */
<b class="fc"><i class="no-highlight">67</i>&nbsp;	private static final AtomicLong ID_GENERATOR = new AtomicLong(0);</b>
<i class="no-highlight">68</i>&nbsp;
<i class="no-highlight">69</i>&nbsp;	/**
<i class="no-highlight">70</i>&nbsp;	 * A unique identifier, used to distinguish or compare the tree nodes
<i class="no-highlight">71</i>&nbsp;	 */
<b class="fc"><i class="no-highlight">72</i>&nbsp;	private final long id = ID_GENERATOR.getAndIncrement();</b>
<i class="no-highlight">73</i>&nbsp;
<i class="no-highlight">74</i>&nbsp;	/**
<i class="no-highlight">75</i>&nbsp;	 * Reference to the parent tree node. Is {@code null} if the current tree node is root
<i class="no-highlight">76</i>&nbsp;	 */
<i class="no-highlight">77</i>&nbsp;	protected TreeNode&lt;T&gt; parent;
<i class="no-highlight">78</i>&nbsp;
<i class="no-highlight">79</i>&nbsp;	/**
<i class="no-highlight">80</i>&nbsp;	 * Data store in the current tree node
<i class="no-highlight">81</i>&nbsp;	 */
<i class="no-highlight">82</i>&nbsp;	protected T data;
<i class="no-highlight">83</i>&nbsp;
<i class="no-highlight">84</i>&nbsp;	/**
<i class="no-highlight">85</i>&nbsp;	 * Creates an instance of this class
<i class="no-highlight">86</i>&nbsp;	 *
<i class="no-highlight">87</i>&nbsp;	 * @param data data to store in the current tree node
<i class="no-highlight">88</i>&nbsp;	 */
<b class="fc"><i class="no-highlight">89</i>&nbsp;	public TreeNode(T data) {</b>
<b class="fc"><i class="no-highlight">90</i>&nbsp;		this.data = data;</b>
<i class="no-highlight">91</i>&nbsp;	}
<i class="no-highlight">92</i>&nbsp;
<i class="no-highlight">93</i>&nbsp;	/**
<i class="no-highlight">94</i>&nbsp;	 * Creates an instance of this class without setting the {@link #data}
<i class="no-highlight">95</i>&nbsp;	 */
<b class="nc"><i class="no-highlight">96</i>&nbsp;	public TreeNode() {</b>
<i class="no-highlight">97</i>&nbsp;	}
<i class="no-highlight">98</i>&nbsp;
<i class="no-highlight">99</i>&nbsp;	/**
<i class="no-highlight">100</i>&nbsp;	 * Returns the collection of the child nodes of the current node
<i class="no-highlight">101</i>&nbsp;	 * with all of its proper descendants, if any
<i class="no-highlight">102</i>&nbsp;	 * &lt;p&gt;
<i class="no-highlight">103</i>&nbsp;	 * Returns {@link Collections#emptySet()} if the current node is leaf
<i class="no-highlight">104</i>&nbsp;	 *
<i class="no-highlight">105</i>&nbsp;	 * @return collection of the child nodes of the current node with
<i class="no-highlight">106</i>&nbsp;	 *         all of its proper descendants, if any;
<i class="no-highlight">107</i>&nbsp;	 *         {@link Collections#emptySet()} if the current node is leaf
<i class="no-highlight">108</i>&nbsp;	 */
<i class="no-highlight">109</i>&nbsp;	public abstract Collection&lt;? extends TreeNode&lt;T&gt;&gt; subtrees();
<i class="no-highlight">110</i>&nbsp;
<i class="no-highlight">111</i>&nbsp;	/**
<i class="no-highlight">112</i>&nbsp;	 * Adds the subtree with all of its descendants to the current tree node
<i class="no-highlight">113</i>&nbsp;	 * &lt;p&gt;
<i class="no-highlight">114</i>&nbsp;	 * {@code null} subtree cannot be added, in this case return result will
<i class="no-highlight">115</i>&nbsp;	 * be {@code false}
<i class="no-highlight">116</i>&nbsp;	 * &lt;p&gt;
<i class="no-highlight">117</i>&nbsp;	 * Checks whether this tree node was changed as a result of the call
<i class="no-highlight">118</i>&nbsp;	 *
<i class="no-highlight">119</i>&nbsp;	 * @param subtree subtree to add to the current tree node
<i class="no-highlight">120</i>&nbsp;	 * @return {@code true} if this tree node was changed as a
<i class="no-highlight">121</i>&nbsp;	 *         result of the call; {@code false} otherwise
<i class="no-highlight">122</i>&nbsp;	 */
<i class="no-highlight">123</i>&nbsp;	public abstract boolean add(TreeNode&lt;T&gt; subtree);
<i class="no-highlight">124</i>&nbsp;
<i class="no-highlight">125</i>&nbsp;	/**
<i class="no-highlight">126</i>&nbsp;	 * Drops the first occurrence of the specified subtree from the current
<i class="no-highlight">127</i>&nbsp;	 * tree node
<i class="no-highlight">128</i>&nbsp;	 * &lt;p&gt;
<i class="no-highlight">129</i>&nbsp;	 * Checks whether the current tree node was changed as a result of
<i class="no-highlight">130</i>&nbsp;	 * the call
<i class="no-highlight">131</i>&nbsp;	 *
<i class="no-highlight">132</i>&nbsp;	 * @param subtree subtree to drop from the current tree node
<i class="no-highlight">133</i>&nbsp;	 * @return {@code true} if the current tree node was changed as a result
<i class="no-highlight">134</i>&nbsp;	 *         of the call; {@code false} otherwise
<i class="no-highlight">135</i>&nbsp;	 */
<i class="no-highlight">136</i>&nbsp;	public abstract boolean dropSubtree(TreeNode&lt;T&gt; subtree);
<i class="no-highlight">137</i>&nbsp;
<i class="no-highlight">138</i>&nbsp;	/**
<i class="no-highlight">139</i>&nbsp;	 * Removes all the subtrees with all of its descendants from the current
<i class="no-highlight">140</i>&nbsp;	 * tree node
<i class="no-highlight">141</i>&nbsp;	 */
<i class="no-highlight">142</i>&nbsp;	public abstract void clear();
<i class="no-highlight">143</i>&nbsp;
<i class="no-highlight">144</i>&nbsp;	/**
<i class="no-highlight">145</i>&nbsp;	 * Returns an iterator over the elements in this tree in proper sequence
<i class="no-highlight">146</i>&nbsp;	 * &lt;p&gt;
<i class="no-highlight">147</i>&nbsp;	 * The returned iterator is &lt;b&gt;fail-fast&lt;/b&gt;
<i class="no-highlight">148</i>&nbsp;	 *
<i class="no-highlight">149</i>&nbsp;	 * @return an iterator over the elements in this tree in proper sequence
<i class="no-highlight">150</i>&nbsp;	 */
<i class="no-highlight">151</i>&nbsp;	public abstract TreeNodeIterator iterator();
<i class="no-highlight">152</i>&nbsp;
<i class="no-highlight">153</i>&nbsp;	/**
<i class="no-highlight">154</i>&nbsp;	 * Returns the data object stored in the current tree node
<i class="no-highlight">155</i>&nbsp;	 *
<i class="no-highlight">156</i>&nbsp;	 * @return data object stored in the current tree node
<i class="no-highlight">157</i>&nbsp;	 */
<i class="no-highlight">158</i>&nbsp;	public T data() {
<b class="fc"><i class="no-highlight">159</i>&nbsp;		return data;</b>
<i class="no-highlight">160</i>&nbsp;	}
<i class="no-highlight">161</i>&nbsp;
<i class="no-highlight">162</i>&nbsp;	/**
<i class="no-highlight">163</i>&nbsp;	 * Stores the data object into the current tree node
<i class="no-highlight">164</i>&nbsp;	 *
<i class="no-highlight">165</i>&nbsp;	 * @param data data object to store into the current tree node
<i class="no-highlight">166</i>&nbsp;	 */
<i class="no-highlight">167</i>&nbsp;	public void setData(T data) {
<b class="nc"><i class="no-highlight">168</i>&nbsp;		this.data = data;</b>
<i class="no-highlight">169</i>&nbsp;	}
<i class="no-highlight">170</i>&nbsp;
<i class="no-highlight">171</i>&nbsp;	/**
<i class="no-highlight">172</i>&nbsp;	 * Checks whether the current tree node is the root of the tree
<i class="no-highlight">173</i>&nbsp;	 *
<i class="no-highlight">174</i>&nbsp;	 * @return {@code true} if the current tree node is root of the tree;
<i class="no-highlight">175</i>&nbsp;	 *         {@code false} otherwise
<i class="no-highlight">176</i>&nbsp;	 */
<i class="no-highlight">177</i>&nbsp;	public boolean isRoot() {
<b class="fc"><i class="no-highlight">178</i>&nbsp;		return parent == null;</b>
<i class="no-highlight">179</i>&nbsp;	}
<i class="no-highlight">180</i>&nbsp;
<i class="no-highlight">181</i>&nbsp;	/**
<i class="no-highlight">182</i>&nbsp;	 * Returns the root node of the current node
<i class="no-highlight">183</i>&nbsp;	 * &lt;p&gt;
<i class="no-highlight">184</i>&nbsp;	 * Returns itself if the current node is root
<i class="no-highlight">185</i>&nbsp;	 *
<i class="no-highlight">186</i>&nbsp;	 * @return root node of the current node; itself,
<i class="no-highlight">187</i>&nbsp;	 *         if the current node is root
<i class="no-highlight">188</i>&nbsp;	 */
<i class="no-highlight">189</i>&nbsp;	public TreeNode&lt;T&gt; root() {
<b class="fc"><i class="no-highlight">190</i>&nbsp;		if (isRoot()) {</b>
<b class="fc"><i class="no-highlight">191</i>&nbsp;			return this;</b>
<i class="no-highlight">192</i>&nbsp;		}
<b class="nc"><i class="no-highlight">193</i>&nbsp;		TreeNode&lt;T&gt; node = this;</b>
<i class="no-highlight">194</i>&nbsp;		do {
<b class="nc"><i class="no-highlight">195</i>&nbsp;			node = node.parent();</b>
<b class="nc"><i class="no-highlight">196</i>&nbsp;		} while (!node.isRoot());</b>
<b class="nc"><i class="no-highlight">197</i>&nbsp;		return node;</b>
<i class="no-highlight">198</i>&nbsp;	}
<i class="no-highlight">199</i>&nbsp;
<i class="no-highlight">200</i>&nbsp;	/**
<i class="no-highlight">201</i>&nbsp;	 * Returns the parent node of the current node
<i class="no-highlight">202</i>&nbsp;	 * &lt;p&gt;
<i class="no-highlight">203</i>&nbsp;	 * Returns {@code null} if the current node is root
<i class="no-highlight">204</i>&nbsp;	 *
<i class="no-highlight">205</i>&nbsp;	 * @return parent node of the current node; {@code null}
<i class="no-highlight">206</i>&nbsp;	 *         if the current node is root
<i class="no-highlight">207</i>&nbsp;	 */
<i class="no-highlight">208</i>&nbsp;	public TreeNode&lt;T&gt; parent() {
<b class="fc"><i class="no-highlight">209</i>&nbsp;		return parent;</b>
<i class="no-highlight">210</i>&nbsp;	}
<i class="no-highlight">211</i>&nbsp;
<i class="no-highlight">212</i>&nbsp;	/**
<i class="no-highlight">213</i>&nbsp;	 * Checks whether the current tree node is a leaf, e.g. does not have any
<i class="no-highlight">214</i>&nbsp;	 * subtrees
<i class="no-highlight">215</i>&nbsp;	 *
<i class="no-highlight">216</i>&nbsp;	 * @return {@code true} if the current tree node is a leaf, e.g. does not
<i class="no-highlight">217</i>&nbsp;	 *         have any subtrees; {@code false} otherwise
<i class="no-highlight">218</i>&nbsp;	 */
<i class="no-highlight">219</i>&nbsp;	public boolean isLeaf() {
<b class="nc"><i class="no-highlight">220</i>&nbsp;		return subtrees().isEmpty();</b>
<i class="no-highlight">221</i>&nbsp;	}
<i class="no-highlight">222</i>&nbsp;
<i class="no-highlight">223</i>&nbsp;	/**
<i class="no-highlight">224</i>&nbsp;	 * Searches the tree node within the tree, which has the specified data,
<i class="no-highlight">225</i>&nbsp;	 * starting from the current tree node and returns the first occurrence of it
<i class="no-highlight">226</i>&nbsp;	 *
<i class="no-highlight">227</i>&nbsp;	 * @param data data to find the tree node with
<i class="no-highlight">228</i>&nbsp;	 * @return first occurrence of the searched tree node with data specified
<i class="no-highlight">229</i>&nbsp;	 */
<i class="no-highlight">230</i>&nbsp;	@SuppressWarnings(&quot;unchecked&quot;)
<i class="no-highlight">231</i>&nbsp;	public TreeNode&lt;T&gt; find(final T data) {
<b class="nc"><i class="no-highlight">232</i>&nbsp;		if (isLeaf()) {</b>
<b class="nc"><i class="no-highlight">233</i>&nbsp;			return (data() == null ? data == null : data().equals(data)) ? this : null;</b>
<i class="no-highlight">234</i>&nbsp;		}
<b class="nc"><i class="no-highlight">235</i>&nbsp;		final TreeNode&lt;T&gt;[] searchedNode = (TreeNode&lt;T&gt;[]) Array.newInstance(getClass(), 1);</b>
<b class="nc"><i class="no-highlight">236</i>&nbsp;		traversePreOrder(new TraversalAction&lt;TreeNode&lt;T&gt;&gt;() {</b>
<i class="no-highlight">237</i>&nbsp;			@Override
<i class="no-highlight">238</i>&nbsp;			public void perform(TreeNode&lt;T&gt; node) {
<b class="nc"><i class="no-highlight">239</i>&nbsp;				if ((node.data() == null ?</b>
<b class="nc"><i class="no-highlight">240</i>&nbsp;						data == null : node.data().equals(data))) {</b>
<b class="nc"><i class="no-highlight">241</i>&nbsp;					searchedNode[0] = node;</b>
<i class="no-highlight">242</i>&nbsp;				}
<i class="no-highlight">243</i>&nbsp;			}
<i class="no-highlight">244</i>&nbsp;
<i class="no-highlight">245</i>&nbsp;			@Override
<i class="no-highlight">246</i>&nbsp;			public boolean isCompleted() {
<b class="nc"><i class="no-highlight">247</i>&nbsp;				return searchedNode[0] != null;</b>
<i class="no-highlight">248</i>&nbsp;			}
<i class="no-highlight">249</i>&nbsp;		});
<b class="nc"><i class="no-highlight">250</i>&nbsp;		return searchedNode[0];</b>
<i class="no-highlight">251</i>&nbsp;	}
<i class="no-highlight">252</i>&nbsp;
<i class="no-highlight">253</i>&nbsp;	/**
<i class="no-highlight">254</i>&nbsp;	 * Searches the tree nodes within the tree, which have the specified data,
<i class="no-highlight">255</i>&nbsp;	 * starting from the current tree node and returns the collection of the found
<i class="no-highlight">256</i>&nbsp;	 * tree nodes
<i class="no-highlight">257</i>&nbsp;	 *
<i class="no-highlight">258</i>&nbsp;	 * @param data data to find the tree nodes with
<i class="no-highlight">259</i>&nbsp;	 * @return collection of the searched tree nodes with data specified
<i class="no-highlight">260</i>&nbsp;	 */
<i class="no-highlight">261</i>&nbsp;	public Collection&lt;? extends TreeNode&lt;T&gt;&gt; findAll(final T data) {
<b class="nc"><i class="no-highlight">262</i>&nbsp;		if (isLeaf()) {</b>
<b class="nc"><i class="no-highlight">263</i>&nbsp;			return (data() == null ? data == null : data().equals(data)) ?</b>
<b class="nc"><i class="no-highlight">264</i>&nbsp;					Collections.singleton(this) : Collections.&lt;TreeNode&lt;T&gt;&gt;emptySet();</b>
<i class="no-highlight">265</i>&nbsp;		}
<b class="nc"><i class="no-highlight">266</i>&nbsp;		final Collection&lt;TreeNode&lt;T&gt;&gt; searchedNodes = new HashSet&lt;&gt;();</b>
<b class="nc"><i class="no-highlight">267</i>&nbsp;		traversePreOrder(new TraversalAction&lt;TreeNode&lt;T&gt;&gt;() {</b>
<i class="no-highlight">268</i>&nbsp;			@Override
<i class="no-highlight">269</i>&nbsp;			public void perform(TreeNode&lt;T&gt; node) {
<b class="nc"><i class="no-highlight">270</i>&nbsp;				if ((node.data() == null ?</b>
<b class="nc"><i class="no-highlight">271</i>&nbsp;						data == null : node.data().equals(data))) {</b>
<b class="nc"><i class="no-highlight">272</i>&nbsp;					searchedNodes.add(node);</b>
<i class="no-highlight">273</i>&nbsp;				}
<i class="no-highlight">274</i>&nbsp;			}
<i class="no-highlight">275</i>&nbsp;
<i class="no-highlight">276</i>&nbsp;			@Override
<i class="no-highlight">277</i>&nbsp;			public boolean isCompleted() {
<b class="nc"><i class="no-highlight">278</i>&nbsp;				return false;</b>
<i class="no-highlight">279</i>&nbsp;			}
<i class="no-highlight">280</i>&nbsp;		});
<b class="nc"><i class="no-highlight">281</i>&nbsp;		return searchedNodes;</b>
<i class="no-highlight">282</i>&nbsp;	}
<i class="no-highlight">283</i>&nbsp;
<i class="no-highlight">284</i>&nbsp;	/**
<i class="no-highlight">285</i>&nbsp;	 * Checks whether among the current tree node subtrees there is
<i class="no-highlight">286</i>&nbsp;	 * a specified subtree
<i class="no-highlight">287</i>&nbsp;	 *
<i class="no-highlight">288</i>&nbsp;	 * @param subtree subtree whose presence within the current tree
<i class="no-highlight">289</i>&nbsp;	 *                node children is to be checked
<i class="no-highlight">290</i>&nbsp;	 * @return {@code true} if among the current tree node subtrees
<i class="no-highlight">291</i>&nbsp;	 *         there is a specified subtree; {@code false} otherwise
<i class="no-highlight">292</i>&nbsp;	 */
<i class="no-highlight">293</i>&nbsp;	public boolean hasSubtree(TreeNode&lt;T&gt; subtree) {
<b class="nc"><i class="no-highlight">294</i>&nbsp;		if (subtree == null</b>
<b class="nc"><i class="no-highlight">295</i>&nbsp;				|| isLeaf()</b>
<b class="nc"><i class="no-highlight">296</i>&nbsp;				|| subtree.isRoot()) {</b>
<b class="nc"><i class="no-highlight">297</i>&nbsp;			return false;</b>
<i class="no-highlight">298</i>&nbsp;		}
<b class="nc"><i class="no-highlight">299</i>&nbsp;		for (TreeNode&lt;T&gt; mSubtree : subtrees()) {</b>
<b class="nc"><i class="no-highlight">300</i>&nbsp;			if (mSubtree.equals(subtree)) {</b>
<b class="nc"><i class="no-highlight">301</i>&nbsp;				return true;</b>
<i class="no-highlight">302</i>&nbsp;			}
<b class="nc"><i class="no-highlight">303</i>&nbsp;		}</b>
<b class="nc"><i class="no-highlight">304</i>&nbsp;		return false;</b>
<i class="no-highlight">305</i>&nbsp;	}
<i class="no-highlight">306</i>&nbsp;
<i class="no-highlight">307</i>&nbsp;	/**
<i class="no-highlight">308</i>&nbsp;	 * Checks whether the current tree node with all of its descendants
<i class="no-highlight">309</i>&nbsp;	 * (entire tree) contains the specified node
<i class="no-highlight">310</i>&nbsp;	 *
<i class="no-highlight">311</i>&nbsp;	 * @param node node whose presence within the current tree node with
<i class="no-highlight">312</i>&nbsp;	 *             all of its descendants (entire tree) is to be checked
<i class="no-highlight">313</i>&nbsp;	 * @return {@code true} if the current node with all of its descendants
<i class="no-highlight">314</i>&nbsp;	 *         (entire tree) contains the specified node; {@code false}
<i class="no-highlight">315</i>&nbsp;	 *         otherwise
<i class="no-highlight">316</i>&nbsp;	 */
<i class="no-highlight">317</i>&nbsp;	public boolean contains(TreeNode&lt;T&gt; node) {
<b class="nc"><i class="no-highlight">318</i>&nbsp;		if (node == null</b>
<b class="nc"><i class="no-highlight">319</i>&nbsp;				|| isLeaf()</b>
<b class="nc"><i class="no-highlight">320</i>&nbsp;				|| node.isRoot()) {</b>
<b class="nc"><i class="no-highlight">321</i>&nbsp;			return false;</b>
<i class="no-highlight">322</i>&nbsp;		}
<b class="nc"><i class="no-highlight">323</i>&nbsp;		for (TreeNode&lt;T&gt; subtree : subtrees()) {</b>
<b class="nc"><i class="no-highlight">324</i>&nbsp;			if (subtree.equals(node)</b>
<b class="nc"><i class="no-highlight">325</i>&nbsp;					|| subtree.contains(node)) {</b>
<b class="nc"><i class="no-highlight">326</i>&nbsp;				return true;</b>
<i class="no-highlight">327</i>&nbsp;			}
<b class="nc"><i class="no-highlight">328</i>&nbsp;		}</b>
<b class="nc"><i class="no-highlight">329</i>&nbsp;		return false;</b>
<i class="no-highlight">330</i>&nbsp;	}
<i class="no-highlight">331</i>&nbsp;
<i class="no-highlight">332</i>&nbsp;	/**
<i class="no-highlight">333</i>&nbsp;	 * Checks whether the current tree node with all of its descendants
<i class="no-highlight">334</i>&nbsp;	 * (entire tree) contains all of the nodes from the specified collection
<i class="no-highlight">335</i>&nbsp;	 * (the place of nodes within a tree is not important)
<i class="no-highlight">336</i>&nbsp;	 *
<i class="no-highlight">337</i>&nbsp;	 * @param nodes collection of nodes to be checked for containment
<i class="no-highlight">338</i>&nbsp;	 *              within the current tree node with all of its descendants
<i class="no-highlight">339</i>&nbsp;	 *              (entire tree)
<i class="no-highlight">340</i>&nbsp;	 * @return {@code true} if the current tree node with all of its
<i class="no-highlight">341</i>&nbsp;	 *         descendants (entire tree) contains all of the nodes from the
<i class="no-highlight">342</i>&nbsp;	 *         specified collection; {@code false} otherwise
<i class="no-highlight">343</i>&nbsp;	 */
<i class="no-highlight">344</i>&nbsp;	public boolean containsAll(Collection&lt;TreeNode&lt;T&gt;&gt; nodes) {
<b class="nc"><i class="no-highlight">345</i>&nbsp;		if (isLeaf()</b>
<b class="nc"><i class="no-highlight">346</i>&nbsp;				|| areAllNulls(nodes)) {</b>
<b class="nc"><i class="no-highlight">347</i>&nbsp;			return false;</b>
<i class="no-highlight">348</i>&nbsp;		}
<b class="nc"><i class="no-highlight">349</i>&nbsp;		for (TreeNode&lt;T&gt; node : nodes) {</b>
<b class="nc"><i class="no-highlight">350</i>&nbsp;			if (!contains(node)) {</b>
<b class="nc"><i class="no-highlight">351</i>&nbsp;				return false;</b>
<i class="no-highlight">352</i>&nbsp;			}
<b class="nc"><i class="no-highlight">353</i>&nbsp;		}</b>
<b class="nc"><i class="no-highlight">354</i>&nbsp;		return true;</b>
<i class="no-highlight">355</i>&nbsp;	}
<i class="no-highlight">356</i>&nbsp;
<i class="no-highlight">357</i>&nbsp;	/**
<i class="no-highlight">358</i>&nbsp;	 * Removes the first occurrence of the specified node from the entire tree,
<i class="no-highlight">359</i>&nbsp;	 * starting from the current tree node and traversing in a pre order manner
<i class="no-highlight">360</i>&nbsp;	 * &lt;p&gt;
<i class="no-highlight">361</i>&nbsp;	 * Checks whether the current tree node was changed as a result of the call
<i class="no-highlight">362</i>&nbsp;	 *
<i class="no-highlight">363</i>&nbsp;	 * @param node node to remove from the entire tree
<i class="no-highlight">364</i>&nbsp;	 * @return {@code true} if the current tree node was changed as a result of
<i class="no-highlight">365</i>&nbsp;	 *         the call; {@code false} otherwise
<i class="no-highlight">366</i>&nbsp;	 */
<i class="no-highlight">367</i>&nbsp;	public boolean remove(TreeNode&lt;T&gt; node) {
<b class="nc"><i class="no-highlight">368</i>&nbsp;		if (node == null</b>
<b class="nc"><i class="no-highlight">369</i>&nbsp;				|| isLeaf()</b>
<b class="nc"><i class="no-highlight">370</i>&nbsp;				|| node.isRoot()) {</b>
<b class="nc"><i class="no-highlight">371</i>&nbsp;			return false;</b>
<i class="no-highlight">372</i>&nbsp;		}
<b class="nc"><i class="no-highlight">373</i>&nbsp;		if (dropSubtree(node)) {</b>
<b class="nc"><i class="no-highlight">374</i>&nbsp;			return true;</b>
<i class="no-highlight">375</i>&nbsp;		}
<b class="nc"><i class="no-highlight">376</i>&nbsp;		for (TreeNode&lt;T&gt; subtree : subtrees()) {</b>
<b class="nc"><i class="no-highlight">377</i>&nbsp;			if (subtree.remove(node)) {</b>
<b class="nc"><i class="no-highlight">378</i>&nbsp;				return true;</b>
<i class="no-highlight">379</i>&nbsp;			}
<b class="nc"><i class="no-highlight">380</i>&nbsp;		}</b>
<b class="nc"><i class="no-highlight">381</i>&nbsp;		return false;</b>
<i class="no-highlight">382</i>&nbsp;	}
<i class="no-highlight">383</i>&nbsp;
<i class="no-highlight">384</i>&nbsp;	/**
<i class="no-highlight">385</i>&nbsp;	 * Removes all of the collection&#39;s nodes from the entire tree, starting from
<i class="no-highlight">386</i>&nbsp;	 * the current tree node and traversing in a pre order manner
<i class="no-highlight">387</i>&nbsp;	 * &lt;p&gt;
<i class="no-highlight">388</i>&nbsp;	 * Checks whether the current tree node was changed as a result of the call
<i class="no-highlight">389</i>&nbsp;	 *
<i class="no-highlight">390</i>&nbsp;	 * @param nodes collection containing nodes to be removed from the entire tree
<i class="no-highlight">391</i>&nbsp;	 * @return {@code true} if the current tree node was changed as a result
<i class="no-highlight">392</i>&nbsp;	 *         of the call; {@code false} otherwise
<i class="no-highlight">393</i>&nbsp;	 */
<i class="no-highlight">394</i>&nbsp;	public boolean removeAll(Collection&lt;TreeNode&lt;T&gt;&gt; nodes) {
<b class="nc"><i class="no-highlight">395</i>&nbsp;		if (isLeaf()</b>
<b class="nc"><i class="no-highlight">396</i>&nbsp;				|| areAllNulls(nodes)) {</b>
<b class="nc"><i class="no-highlight">397</i>&nbsp;			return false;</b>
<i class="no-highlight">398</i>&nbsp;		}
<b class="nc"><i class="no-highlight">399</i>&nbsp;		boolean result = false;</b>
<b class="nc"><i class="no-highlight">400</i>&nbsp;		for (TreeNode&lt;T&gt; node : nodes) {</b>
<b class="nc"><i class="no-highlight">401</i>&nbsp;			boolean currentResult = remove(node);</b>
<b class="nc"><i class="no-highlight">402</i>&nbsp;			if (!result &amp;&amp; currentResult) {</b>
<b class="nc"><i class="no-highlight">403</i>&nbsp;				result = true;</b>
<i class="no-highlight">404</i>&nbsp;			}
<b class="nc"><i class="no-highlight">405</i>&nbsp;		}</b>
<b class="nc"><i class="no-highlight">406</i>&nbsp;		return result;</b>
<i class="no-highlight">407</i>&nbsp;	}
<i class="no-highlight">408</i>&nbsp;
<i class="no-highlight">409</i>&nbsp;	/**
<i class="no-highlight">410</i>&nbsp;	 * Traverses the tree in a pre ordered manner starting from the
<i class="no-highlight">411</i>&nbsp;	 * current tree node and performs the traversal action on each
<i class="no-highlight">412</i>&nbsp;	 * traversed tree node
<i class="no-highlight">413</i>&nbsp;	 *
<i class="no-highlight">414</i>&nbsp;	 * @param action action, which is to be performed on each tree
<i class="no-highlight">415</i>&nbsp;	 *               node, while traversing the tree
<i class="no-highlight">416</i>&nbsp;	 */
<i class="no-highlight">417</i>&nbsp;	public void traversePreOrder(TraversalAction&lt;TreeNode&lt;T&gt;&gt; action) {
<b class="nc"><i class="no-highlight">418</i>&nbsp;		if (!action.isCompleted()) {</b>
<b class="nc"><i class="no-highlight">419</i>&nbsp;			action.perform(this);</b>
<b class="nc"><i class="no-highlight">420</i>&nbsp;			if (!isLeaf()) {</b>
<b class="nc"><i class="no-highlight">421</i>&nbsp;				for (TreeNode&lt;T&gt; subtree : subtrees()) {</b>
<b class="nc"><i class="no-highlight">422</i>&nbsp;					subtree.traversePreOrder(action);</b>
<b class="nc"><i class="no-highlight">423</i>&nbsp;				}</b>
<i class="no-highlight">424</i>&nbsp;			}
<i class="no-highlight">425</i>&nbsp;		}
<i class="no-highlight">426</i>&nbsp;	}
<i class="no-highlight">427</i>&nbsp;
<i class="no-highlight">428</i>&nbsp;	/**
<i class="no-highlight">429</i>&nbsp;	 * Traverses the tree in a post ordered manner starting from the
<i class="no-highlight">430</i>&nbsp;	 * current tree node and performs the traversal action on each
<i class="no-highlight">431</i>&nbsp;	 * traversed tree node
<i class="no-highlight">432</i>&nbsp;	 *
<i class="no-highlight">433</i>&nbsp;	 * @param action action, which is to be performed on each tree
<i class="no-highlight">434</i>&nbsp;	 *               node, while traversing the tree
<i class="no-highlight">435</i>&nbsp;	 */
<i class="no-highlight">436</i>&nbsp;	public void traversePostOrder(TraversalAction&lt;TreeNode&lt;T&gt;&gt; action) {
<b class="nc"><i class="no-highlight">437</i>&nbsp;		if (!action.isCompleted()) {</b>
<b class="nc"><i class="no-highlight">438</i>&nbsp;			if (!isLeaf()) {</b>
<b class="nc"><i class="no-highlight">439</i>&nbsp;				for (TreeNode&lt;T&gt; subtree : subtrees()) {</b>
<b class="nc"><i class="no-highlight">440</i>&nbsp;					subtree.traversePostOrder(action);</b>
<b class="nc"><i class="no-highlight">441</i>&nbsp;				}</b>
<i class="no-highlight">442</i>&nbsp;			}
<b class="nc"><i class="no-highlight">443</i>&nbsp;			action.perform(this);</b>
<i class="no-highlight">444</i>&nbsp;		}
<i class="no-highlight">445</i>&nbsp;	}
<i class="no-highlight">446</i>&nbsp;
<i class="no-highlight">447</i>&nbsp;	/**
<i class="no-highlight">448</i>&nbsp;	 * Returns the pre ordered collection of nodes of the current tree
<i class="no-highlight">449</i>&nbsp;	 * starting from the current tree node
<i class="no-highlight">450</i>&nbsp;	 *
<i class="no-highlight">451</i>&nbsp;	 * @return pre ordered collection of nodes of the current tree starting
<i class="no-highlight">452</i>&nbsp;	 *         from the current tree node
<i class="no-highlight">453</i>&nbsp;	 */
<i class="no-highlight">454</i>&nbsp;	public Collection&lt;TreeNode&lt;T&gt;&gt; preOrdered() {
<b class="nc"><i class="no-highlight">455</i>&nbsp;		if (isLeaf()) {</b>
<b class="nc"><i class="no-highlight">456</i>&nbsp;			return Collections.singleton(this);</b>
<i class="no-highlight">457</i>&nbsp;		}
<b class="nc"><i class="no-highlight">458</i>&nbsp;		final Collection&lt;TreeNode&lt;T&gt;&gt; mPreOrdered = new ArrayList&lt;&gt;();</b>
<b class="nc"><i class="no-highlight">459</i>&nbsp;		TraversalAction&lt;TreeNode&lt;T&gt;&gt; action = populateAction(mPreOrdered);</b>
<b class="nc"><i class="no-highlight">460</i>&nbsp;		traversePreOrder(action);</b>
<b class="nc"><i class="no-highlight">461</i>&nbsp;		return mPreOrdered;</b>
<i class="no-highlight">462</i>&nbsp;	}
<i class="no-highlight">463</i>&nbsp;
<i class="no-highlight">464</i>&nbsp;	/**
<i class="no-highlight">465</i>&nbsp;	 * Returns the post ordered collection of nodes of the current tree
<i class="no-highlight">466</i>&nbsp;	 * starting from the current tree node
<i class="no-highlight">467</i>&nbsp;	 *
<i class="no-highlight">468</i>&nbsp;	 * @return post ordered collection of nodes of the current tree starting
<i class="no-highlight">469</i>&nbsp;	 *         from the current tree node
<i class="no-highlight">470</i>&nbsp;	 */
<i class="no-highlight">471</i>&nbsp;	public Collection&lt;TreeNode&lt;T&gt;&gt; postOrdered() {
<b class="nc"><i class="no-highlight">472</i>&nbsp;		if (isLeaf()) {</b>
<b class="nc"><i class="no-highlight">473</i>&nbsp;			return Collections.singleton(this);</b>
<i class="no-highlight">474</i>&nbsp;		}
<b class="nc"><i class="no-highlight">475</i>&nbsp;		final Collection&lt;TreeNode&lt;T&gt;&gt; mPostOrdered = new ArrayList&lt;&gt;();</b>
<b class="nc"><i class="no-highlight">476</i>&nbsp;		TraversalAction&lt;TreeNode&lt;T&gt;&gt; action = populateAction(mPostOrdered);</b>
<b class="nc"><i class="no-highlight">477</i>&nbsp;		traversePostOrder(action);</b>
<b class="nc"><i class="no-highlight">478</i>&nbsp;		return mPostOrdered;</b>
<i class="no-highlight">479</i>&nbsp;	}
<i class="no-highlight">480</i>&nbsp;
<i class="no-highlight">481</i>&nbsp;	/**
<i class="no-highlight">482</i>&nbsp;	 * Returns the collection of nodes, which connect the current node
<i class="no-highlight">483</i>&nbsp;	 * with its descendants
<i class="no-highlight">484</i>&nbsp;	 *
<i class="no-highlight">485</i>&nbsp;	 * @param descendant the bottom child node for which the path is calculated
<i class="no-highlight">486</i>&nbsp;	 * @return collection of nodes, which connect the current node with its descendants
<i class="no-highlight">487</i>&nbsp;	 * @throws TreeNodeException exception that may be thrown in case if the
<i class="no-highlight">488</i>&nbsp;	 *                           current node does not have such descendant or if the
<i class="no-highlight">489</i>&nbsp;	 *                           specified tree node is root
<i class="no-highlight">490</i>&nbsp;	 */
<i class="no-highlight">491</i>&nbsp;	public Collection&lt;? extends TreeNode&lt;T&gt;&gt; path(TreeNode&lt;T&gt; descendant) {
<b class="nc"><i class="no-highlight">492</i>&nbsp;		if (descendant == null</b>
<b class="nc"><i class="no-highlight">493</i>&nbsp;				|| isLeaf()</b>
<b class="nc"><i class="no-highlight">494</i>&nbsp;				|| this.equals(descendant)) {</b>
<b class="nc"><i class="no-highlight">495</i>&nbsp;			return Collections.singletonList(this);</b>
<i class="no-highlight">496</i>&nbsp;		}
<b class="nc"><i class="no-highlight">497</i>&nbsp;		String errorMessage = &quot;Unable to build the path between tree nodes. &quot;;</b>
<b class="nc"><i class="no-highlight">498</i>&nbsp;		if (descendant.isRoot()) {</b>
<b class="nc"><i class="no-highlight">499</i>&nbsp;			String message = String.format(errorMessage + &quot;Current node %1$s is root&quot;, descendant);</b>
<b class="nc"><i class="no-highlight">500</i>&nbsp;			throw new TreeNodeException(message);</b>
<i class="no-highlight">501</i>&nbsp;		}
<b class="nc"><i class="no-highlight">502</i>&nbsp;		List&lt;TreeNode&lt;T&gt;&gt; path = new LinkedList&lt;&gt;();</b>
<b class="nc"><i class="no-highlight">503</i>&nbsp;		TreeNode&lt;T&gt; node = descendant;</b>
<b class="nc"><i class="no-highlight">504</i>&nbsp;		path.add(node);</b>
<i class="no-highlight">505</i>&nbsp;		do {
<b class="nc"><i class="no-highlight">506</i>&nbsp;			node = node.parent();</b>
<b class="nc"><i class="no-highlight">507</i>&nbsp;			path.add(0, node);</b>
<b class="nc"><i class="no-highlight">508</i>&nbsp;			if (this.equals(node)) {</b>
<b class="nc"><i class="no-highlight">509</i>&nbsp;				return path;</b>
<i class="no-highlight">510</i>&nbsp;			}
<b class="nc"><i class="no-highlight">511</i>&nbsp;		} while (!node.isRoot());</b>
<b class="nc"><i class="no-highlight">512</i>&nbsp;		String message = String.format(errorMessage +</b>
<i class="no-highlight">513</i>&nbsp;				&quot;The specified tree node %1$s is not the descendant of tree node %2$s&quot;, descendant, this);
<b class="nc"><i class="no-highlight">514</i>&nbsp;		throw new TreeNodeException(message);</b>
<i class="no-highlight">515</i>&nbsp;	}
<i class="no-highlight">516</i>&nbsp;
<i class="no-highlight">517</i>&nbsp;	/**
<i class="no-highlight">518</i>&nbsp;	 * Returns the common ancestor of the current node and the node specified
<i class="no-highlight">519</i>&nbsp;	 *
<i class="no-highlight">520</i>&nbsp;	 * @param node node, which the common ancestor is determined for,
<i class="no-highlight">521</i>&nbsp;	 *             along with the current node
<i class="no-highlight">522</i>&nbsp;	 * @return common ancestor of the current node and the node specified
<i class="no-highlight">523</i>&nbsp;	 * @throws TreeNodeException exception that may be thrown in case if the
<i class="no-highlight">524</i>&nbsp;	 *                          specified tree node is null or the specified tree node
<i class="no-highlight">525</i>&nbsp;	 *                          does not belong to the current tree or if any of the tree
<i class="no-highlight">526</i>&nbsp;	 *                          nodes either the current one or the specified one is root
<i class="no-highlight">527</i>&nbsp;	 */
<i class="no-highlight">528</i>&nbsp;	public TreeNode&lt;T&gt; commonAncestor(TreeNode&lt;T&gt; node) {
<b class="nc"><i class="no-highlight">529</i>&nbsp;		String errorMessage = &quot;Unable to find the common ancestor between tree nodes. &quot;;</b>
<b class="nc"><i class="no-highlight">530</i>&nbsp;		if (node == null) {</b>
<b class="nc"><i class="no-highlight">531</i>&nbsp;			String message = errorMessage + &quot;The specified tree node is null&quot;;</b>
<b class="nc"><i class="no-highlight">532</i>&nbsp;			throw new TreeNodeException(message);</b>
<i class="no-highlight">533</i>&nbsp;		}
<b class="nc"><i class="no-highlight">534</i>&nbsp;		if (!this.root().contains(node)) {</b>
<b class="nc"><i class="no-highlight">535</i>&nbsp;			String message = String.format(errorMessage +</b>
<i class="no-highlight">536</i>&nbsp;					&quot;The specified tree node %1$s was not found in the current tree node %2$s&quot;, node, this);
<b class="nc"><i class="no-highlight">537</i>&nbsp;			throw new TreeNodeException(message);</b>
<i class="no-highlight">538</i>&nbsp;		}
<b class="nc"><i class="no-highlight">539</i>&nbsp;		if (this.isRoot()</b>
<b class="nc"><i class="no-highlight">540</i>&nbsp;				|| node.isRoot()) {</b>
<b class="nc"><i class="no-highlight">541</i>&nbsp;			String message = String.format(errorMessage + &quot;The tree node %1$s is root&quot;, this.isRoot() ? this : node);</b>
<b class="nc"><i class="no-highlight">542</i>&nbsp;			throw new TreeNodeException(message);</b>
<i class="no-highlight">543</i>&nbsp;		}
<b class="nc"><i class="no-highlight">544</i>&nbsp;		if (this.equals(node)</b>
<b class="nc"><i class="no-highlight">545</i>&nbsp;				|| node.isSiblingOf(this)) {</b>
<b class="nc"><i class="no-highlight">546</i>&nbsp;			return parent();</b>
<i class="no-highlight">547</i>&nbsp;		}
<b class="nc"><i class="no-highlight">548</i>&nbsp;		int thisNodeLevel = this.level();</b>
<b class="nc"><i class="no-highlight">549</i>&nbsp;		int thatNodeLevel = node.level();</b>
<b class="nc"><i class="no-highlight">550</i>&nbsp;		return thisNodeLevel &gt; thatNodeLevel ? node.parent() : this.parent();</b>
<i class="no-highlight">551</i>&nbsp;	}
<i class="no-highlight">552</i>&nbsp;
<i class="no-highlight">553</i>&nbsp;	/**
<i class="no-highlight">554</i>&nbsp;	 * Checks whether the current tree node is a sibling of the specified node,
<i class="no-highlight">555</i>&nbsp;	 * e.g. whether the current tree node and the specified one both have the
<i class="no-highlight">556</i>&nbsp;	 * same parent
<i class="no-highlight">557</i>&nbsp;	 *
<i class="no-highlight">558</i>&nbsp;	 * @param node node, which sibling with the current tree node is to be checked
<i class="no-highlight">559</i>&nbsp;	 * @return {@code true} if the current tree node is a sibling of the specified
<i class="no-highlight">560</i>&nbsp;	 *         node, e.g. whether the current tree node and the specified one both
<i class="no-highlight">561</i>&nbsp;	 *         have the same parent; {@code false} otherwise
<i class="no-highlight">562</i>&nbsp;	 */
<i class="no-highlight">563</i>&nbsp;	public boolean isSiblingOf(TreeNode&lt;T&gt; node) {
<b class="nc"><i class="no-highlight">564</i>&nbsp;		return node != null</b>
<b class="nc"><i class="no-highlight">565</i>&nbsp;				&amp;&amp; !isRoot()</b>
<b class="nc"><i class="no-highlight">566</i>&nbsp;				&amp;&amp; !node.isRoot()</b>
<b class="nc"><i class="no-highlight">567</i>&nbsp;				&amp;&amp; this.parent().equals(node.parent());</b>
<i class="no-highlight">568</i>&nbsp;	}
<i class="no-highlight">569</i>&nbsp;
<i class="no-highlight">570</i>&nbsp;	/**
<i class="no-highlight">571</i>&nbsp;	 * Checks whether the current tree node is the ancestor of the node specified
<i class="no-highlight">572</i>&nbsp;	 *
<i class="no-highlight">573</i>&nbsp;	 * @param node node, which is checked to be the descendant of the current tree
<i class="no-highlight">574</i>&nbsp;	 *             node
<i class="no-highlight">575</i>&nbsp;	 * @return {@code true} if the current tree node is the ancestor of the node
<i class="no-highlight">576</i>&nbsp;	 *         specified; {@code false} otherwise
<i class="no-highlight">577</i>&nbsp;	 */
<i class="no-highlight">578</i>&nbsp;	public boolean isAncestorOf(TreeNode&lt;T&gt; node) {
<b class="nc"><i class="no-highlight">579</i>&nbsp;		if (node == null</b>
<b class="nc"><i class="no-highlight">580</i>&nbsp;				|| isLeaf()</b>
<b class="nc"><i class="no-highlight">581</i>&nbsp;				|| node.isRoot()</b>
<b class="nc"><i class="no-highlight">582</i>&nbsp;				|| this.equals(node)) {</b>
<b class="nc"><i class="no-highlight">583</i>&nbsp;			return false;</b>
<i class="no-highlight">584</i>&nbsp;		}
<b class="nc"><i class="no-highlight">585</i>&nbsp;		TreeNode&lt;T&gt; mNode = node;</b>
<i class="no-highlight">586</i>&nbsp;		do {
<b class="nc"><i class="no-highlight">587</i>&nbsp;			mNode = mNode.parent();</b>
<b class="nc"><i class="no-highlight">588</i>&nbsp;			if (this.equals(mNode)) {</b>
<b class="nc"><i class="no-highlight">589</i>&nbsp;				return true;</b>
<i class="no-highlight">590</i>&nbsp;			}
<b class="nc"><i class="no-highlight">591</i>&nbsp;		} while (!mNode.isRoot());</b>
<b class="nc"><i class="no-highlight">592</i>&nbsp;		return false;</b>
<i class="no-highlight">593</i>&nbsp;	}
<i class="no-highlight">594</i>&nbsp;
<i class="no-highlight">595</i>&nbsp;	/**
<i class="no-highlight">596</i>&nbsp;	 * Checks whether the current tree node is the descendant of the node specified
<i class="no-highlight">597</i>&nbsp;	 *
<i class="no-highlight">598</i>&nbsp;	 * @param node node, which is checked to be the ancestor of the current tree
<i class="no-highlight">599</i>&nbsp;	 *             node
<i class="no-highlight">600</i>&nbsp;	 * @return {@code true} if the current tree node is the ancestor of the node
<i class="no-highlight">601</i>&nbsp;	 *         specified; {@code false} otherwise
<i class="no-highlight">602</i>&nbsp;	 */
<i class="no-highlight">603</i>&nbsp;	public boolean isDescendantOf(TreeNode&lt;T&gt; node) {
<b class="nc"><i class="no-highlight">604</i>&nbsp;		if (node == null</b>
<b class="nc"><i class="no-highlight">605</i>&nbsp;				|| this.isRoot()</b>
<b class="nc"><i class="no-highlight">606</i>&nbsp;				|| node.isLeaf()</b>
<b class="nc"><i class="no-highlight">607</i>&nbsp;				|| this.equals(node)) {</b>
<b class="nc"><i class="no-highlight">608</i>&nbsp;			return false;</b>
<i class="no-highlight">609</i>&nbsp;		}
<b class="nc"><i class="no-highlight">610</i>&nbsp;		TreeNode&lt;T&gt; mNode = this;</b>
<i class="no-highlight">611</i>&nbsp;		do {
<b class="nc"><i class="no-highlight">612</i>&nbsp;			mNode = mNode.parent();</b>
<b class="nc"><i class="no-highlight">613</i>&nbsp;			if (node.equals(mNode)) {</b>
<b class="nc"><i class="no-highlight">614</i>&nbsp;				return true;</b>
<i class="no-highlight">615</i>&nbsp;			}
<b class="nc"><i class="no-highlight">616</i>&nbsp;		} while (!mNode.isRoot());</b>
<b class="nc"><i class="no-highlight">617</i>&nbsp;		return false;</b>
<i class="no-highlight">618</i>&nbsp;	}
<i class="no-highlight">619</i>&nbsp;
<i class="no-highlight">620</i>&nbsp;	/**
<i class="no-highlight">621</i>&nbsp;	 * Returns the number of nodes in the entire tree, including the current tree node
<i class="no-highlight">622</i>&nbsp;	 *
<i class="no-highlight">623</i>&nbsp;	 * @return number of nodes in the entire tree, including the current tree node
<i class="no-highlight">624</i>&nbsp;	 */
<i class="no-highlight">625</i>&nbsp;	public long size() {
<b class="nc"><i class="no-highlight">626</i>&nbsp;		if (isLeaf()) {</b>
<b class="nc"><i class="no-highlight">627</i>&nbsp;			return 1;</b>
<i class="no-highlight">628</i>&nbsp;		}
<b class="nc"><i class="no-highlight">629</i>&nbsp;		final long[] count = {0};</b>
<b class="nc"><i class="no-highlight">630</i>&nbsp;		TraversalAction&lt;TreeNode&lt;T&gt;&gt; action = new TraversalAction&lt;TreeNode&lt;T&gt;&gt;() {</b>
<i class="no-highlight">631</i>&nbsp;			@Override
<i class="no-highlight">632</i>&nbsp;			public void perform(TreeNode&lt;T&gt; node) {
<b class="nc"><i class="no-highlight">633</i>&nbsp;				count[0]++;</b>
<i class="no-highlight">634</i>&nbsp;			}
<i class="no-highlight">635</i>&nbsp;
<i class="no-highlight">636</i>&nbsp;			@Override
<i class="no-highlight">637</i>&nbsp;			public boolean isCompleted() {
<b class="nc"><i class="no-highlight">638</i>&nbsp;				return false;</b>
<i class="no-highlight">639</i>&nbsp;			}
<i class="no-highlight">640</i>&nbsp;		};
<b class="nc"><i class="no-highlight">641</i>&nbsp;		traversePreOrder(action);</b>
<b class="nc"><i class="no-highlight">642</i>&nbsp;		return count[0];</b>
<i class="no-highlight">643</i>&nbsp;	}
<i class="no-highlight">644</i>&nbsp;
<i class="no-highlight">645</i>&nbsp;	/**
<i class="no-highlight">646</i>&nbsp;	 * Returns the height of the current tree node, e.g. the number of edges
<i class="no-highlight">647</i>&nbsp;	 * on the longest downward path between that node and a leaf
<i class="no-highlight">648</i>&nbsp;	 *
<i class="no-highlight">649</i>&nbsp;	 * @return height of the current tree node, e.g. the number of edges
<i class="no-highlight">650</i>&nbsp;	 * on the longest downward path between that node and a leaf
<i class="no-highlight">651</i>&nbsp;	 */
<i class="no-highlight">652</i>&nbsp;	public int height() {
<b class="nc"><i class="no-highlight">653</i>&nbsp;		if (isLeaf()) {</b>
<b class="nc"><i class="no-highlight">654</i>&nbsp;			return 0;</b>
<i class="no-highlight">655</i>&nbsp;		}
<b class="nc"><i class="no-highlight">656</i>&nbsp;		int height = 0;</b>
<b class="nc"><i class="no-highlight">657</i>&nbsp;		for (TreeNode&lt;T&gt; subtree : subtrees()) {</b>
<b class="nc"><i class="no-highlight">658</i>&nbsp;			height = Math.max(height, subtree.height());</b>
<b class="nc"><i class="no-highlight">659</i>&nbsp;		}</b>
<b class="nc"><i class="no-highlight">660</i>&nbsp;		return height + 1;</b>
<i class="no-highlight">661</i>&nbsp;	}
<i class="no-highlight">662</i>&nbsp;
<i class="no-highlight">663</i>&nbsp;	/**
<i class="no-highlight">664</i>&nbsp;	 * Returns the depth (level) of the current tree node within the entire tree,
<i class="no-highlight">665</i>&nbsp;	 * e.g. the number of edges between the root tree node and the current one
<i class="no-highlight">666</i>&nbsp;	 *
<i class="no-highlight">667</i>&nbsp;	 * @return depth (level) of the current tree node within the entire tree,
<i class="no-highlight">668</i>&nbsp;	 *         e.g. the number of edges between the root tree node and the current
<i class="no-highlight">669</i>&nbsp;	 *         one
<i class="no-highlight">670</i>&nbsp;	 */
<i class="no-highlight">671</i>&nbsp;	public int level() {
<b class="fc"><i class="no-highlight">672</i>&nbsp;		if (isRoot()) {</b>
<b class="fc"><i class="no-highlight">673</i>&nbsp;			return 0;</b>
<i class="no-highlight">674</i>&nbsp;		}
<b class="fc"><i class="no-highlight">675</i>&nbsp;		int level = 0;</b>
<b class="fc"><i class="no-highlight">676</i>&nbsp;		TreeNode&lt;T&gt; node = this;</b>
<i class="no-highlight">677</i>&nbsp;		do {
<b class="fc"><i class="no-highlight">678</i>&nbsp;			node = node.parent();</b>
<b class="fc"><i class="no-highlight">679</i>&nbsp;			level++;</b>
<b class="fc"><i class="no-highlight">680</i>&nbsp;		} while (!node.isRoot());</b>
<b class="fc"><i class="no-highlight">681</i>&nbsp;		return level;</b>
<i class="no-highlight">682</i>&nbsp;	}
<i class="no-highlight">683</i>&nbsp;
<i class="no-highlight">684</i>&nbsp;	/**
<i class="no-highlight">685</i>&nbsp;	 * Creates and returns a copy of this object
<i class="no-highlight">686</i>&nbsp;	 *
<i class="no-highlight">687</i>&nbsp;	 * @return a clone of this instance
<i class="no-highlight">688</i>&nbsp;	 */
<i class="no-highlight">689</i>&nbsp;	@SuppressWarnings(&quot;unchecked&quot;)
<i class="no-highlight">690</i>&nbsp;	@Override
<i class="no-highlight">691</i>&nbsp;	public TreeNode&lt;T&gt; clone() {
<i class="no-highlight">692</i>&nbsp;		try {
<b class="nc"><i class="no-highlight">693</i>&nbsp;			return (TreeNode&lt;T&gt;) super.clone();</b>
<b class="nc"><i class="no-highlight">694</i>&nbsp;		} catch (CloneNotSupportedException e) {</b>
<b class="nc"><i class="no-highlight">695</i>&nbsp;			String message = &quot;Unable to clone the current tree node&quot;;</b>
<b class="nc"><i class="no-highlight">696</i>&nbsp;			throw new TreeNodeException(message, e);</b>
<i class="no-highlight">697</i>&nbsp;		}
<i class="no-highlight">698</i>&nbsp;	}
<i class="no-highlight">699</i>&nbsp;
<i class="no-highlight">700</i>&nbsp;	/**
<i class="no-highlight">701</i>&nbsp;	 * Indicates whether some object equals to this one
<i class="no-highlight">702</i>&nbsp;	 *
<i class="no-highlight">703</i>&nbsp;	 * @param obj the reference object with which to compare
<i class="no-highlight">704</i>&nbsp;	 * @return {@code true} if this object is the same as the obj
<i class="no-highlight">705</i>&nbsp;	 *         argument; {@code false} otherwise
<i class="no-highlight">706</i>&nbsp;	 */
<i class="no-highlight">707</i>&nbsp;	@SuppressWarnings(&quot;unchecked&quot;)
<i class="no-highlight">708</i>&nbsp;	@Override
<i class="no-highlight">709</i>&nbsp;	public boolean equals(Object obj) {
<b class="fc"><i class="no-highlight">710</i>&nbsp;		if (this == obj) {</b>
<b class="fc"><i class="no-highlight">711</i>&nbsp;			return true;</b>
<i class="no-highlight">712</i>&nbsp;		}
<b class="fc"><i class="no-highlight">713</i>&nbsp;		if (obj == null</b>
<b class="fc"><i class="no-highlight">714</i>&nbsp;				|| getClass() != obj.getClass()) {</b>
<b class="nc"><i class="no-highlight">715</i>&nbsp;			return false;</b>
<i class="no-highlight">716</i>&nbsp;		}
<b class="fc"><i class="no-highlight">717</i>&nbsp;		TreeNode&lt;T&gt; that = (TreeNode&lt;T&gt;) obj;</b>
<b class="fc"><i class="no-highlight">718</i>&nbsp;		return this.id == that.id;</b>
<i class="no-highlight">719</i>&nbsp;	}
<i class="no-highlight">720</i>&nbsp;
<i class="no-highlight">721</i>&nbsp;	/**
<i class="no-highlight">722</i>&nbsp;	 * Returns the hash code value of this object
<i class="no-highlight">723</i>&nbsp;	 *
<i class="no-highlight">724</i>&nbsp;	 * @return hash code value of this object
<i class="no-highlight">725</i>&nbsp;	 */
<i class="no-highlight">726</i>&nbsp;	@Override
<i class="no-highlight">727</i>&nbsp;	public int hashCode() {
<b class="fc"><i class="no-highlight">728</i>&nbsp;		return (int) (this.id ^ (this.id &gt;&gt;&gt; 32));</b>
<i class="no-highlight">729</i>&nbsp;	}
<i class="no-highlight">730</i>&nbsp;
<i class="no-highlight">731</i>&nbsp;	/**
<i class="no-highlight">732</i>&nbsp;	 * Returns the string representation of this object
<i class="no-highlight">733</i>&nbsp;	 *
<i class="no-highlight">734</i>&nbsp;	 * @return string representation of this object
<i class="no-highlight">735</i>&nbsp;	 */
<i class="no-highlight">736</i>&nbsp;	@Override
<i class="no-highlight">737</i>&nbsp;	public String toString() {
<b class="fc"><i class="no-highlight">738</i>&nbsp;		final StringBuilder builder = new StringBuilder();</b>
<b class="fc"><i class="no-highlight">739</i>&nbsp;		builder.append(&quot;\n&quot;);</b>
<b class="fc"><i class="no-highlight">740</i>&nbsp;		final int topNodeLevel = level();</b>
<b class="fc"><i class="no-highlight">741</i>&nbsp;		TraversalAction&lt;TreeNode&lt;T&gt;&gt; action = new TraversalAction&lt;TreeNode&lt;T&gt;&gt;() {</b>
<i class="no-highlight">742</i>&nbsp;			@Override
<i class="no-highlight">743</i>&nbsp;			public void perform(TreeNode&lt;T&gt; node) {
<b class="fc"><i class="no-highlight">744</i>&nbsp;				int nodeLevel = node.level() - topNodeLevel;</b>
<b class="fc"><i class="no-highlight">745</i>&nbsp;				for (int i = 0; i &lt; nodeLevel; i++) {</b>
<b class="fc"><i class="no-highlight">746</i>&nbsp;					builder.append(&quot;|  &quot;);</b>
<i class="no-highlight">747</i>&nbsp;				}
<b class="fc"><i class="no-highlight">748</i>&nbsp;				builder</b>
<b class="fc"><i class="no-highlight">749</i>&nbsp;						.append(&quot;+- &quot;)</b>
<b class="fc"><i class="no-highlight">750</i>&nbsp;						.append(node.data())</b>
<b class="fc"><i class="no-highlight">751</i>&nbsp;						.append(&quot;\n&quot;);</b>
<i class="no-highlight">752</i>&nbsp;			}
<i class="no-highlight">753</i>&nbsp;
<i class="no-highlight">754</i>&nbsp;			@Override
<i class="no-highlight">755</i>&nbsp;			public boolean isCompleted() {
<b class="fc"><i class="no-highlight">756</i>&nbsp;				return false;</b>
<i class="no-highlight">757</i>&nbsp;			}
<i class="no-highlight">758</i>&nbsp;		};
<b class="fc"><i class="no-highlight">759</i>&nbsp;		traversePreOrder(action);</b>
<b class="fc"><i class="no-highlight">760</i>&nbsp;		return builder.toString();</b>
<i class="no-highlight">761</i>&nbsp;	}
<i class="no-highlight">762</i>&nbsp;
<i class="no-highlight">763</i>&nbsp;	/**
<i class="no-highlight">764</i>&nbsp;	 * Populates the input collection with the tree nodes, while traversing the tree
<i class="no-highlight">765</i>&nbsp;	 *
<i class="no-highlight">766</i>&nbsp;	 * @param collection input collection to populate
<i class="no-highlight">767</i>&nbsp;	 * @param &lt;T&gt; type of the tree node
<i class="no-highlight">768</i>&nbsp;	 * @return traversal action, which populates the input collection with the tree nodes
<i class="no-highlight">769</i>&nbsp;	 */
<i class="no-highlight">770</i>&nbsp;	protected static &lt;T&gt; TraversalAction&lt;TreeNode&lt;T&gt;&gt; populateAction(final Collection&lt;TreeNode&lt;T&gt;&gt; collection) {
<b class="nc"><i class="no-highlight">771</i>&nbsp;		return new TraversalAction&lt;TreeNode&lt;T&gt;&gt;() {</b>
<i class="no-highlight">772</i>&nbsp;			@Override
<i class="no-highlight">773</i>&nbsp;			public void perform(TreeNode&lt;T&gt; node) {
<b class="nc"><i class="no-highlight">774</i>&nbsp;				collection.add(node);</b>
<i class="no-highlight">775</i>&nbsp;			}
<i class="no-highlight">776</i>&nbsp;
<i class="no-highlight">777</i>&nbsp;			@Override
<i class="no-highlight">778</i>&nbsp;			public boolean isCompleted() {
<b class="nc"><i class="no-highlight">779</i>&nbsp;				return false;</b>
<i class="no-highlight">780</i>&nbsp;			}
<i class="no-highlight">781</i>&nbsp;		};
<i class="no-highlight">782</i>&nbsp;	}
<i class="no-highlight">783</i>&nbsp;
<i class="no-highlight">784</i>&nbsp;	/**
<i class="no-highlight">785</i>&nbsp;	 * Links the specified parent tree node reference as the parent to the
<i class="no-highlight">786</i>&nbsp;	 * specified tree node
<i class="no-highlight">787</i>&nbsp;	 *
<i class="no-highlight">788</i>&nbsp;	 * @param node tree node to assign the parent tree node reference to
<i class="no-highlight">789</i>&nbsp;	 * @param parent tree node to assign as a parent reference
<i class="no-highlight">790</i>&nbsp;	 * @param &lt;T&gt; type of the data stored in the tree nodes
<i class="no-highlight">791</i>&nbsp;	 */
<i class="no-highlight">792</i>&nbsp;	protected static &lt;T&gt; void linkParent(TreeNode&lt;T&gt; node, TreeNode&lt;T&gt; parent) {
<b class="fc"><i class="no-highlight">793</i>&nbsp;		if (node != null) {</b>
<b class="fc"><i class="no-highlight">794</i>&nbsp;			node.parent = parent;</b>
<i class="no-highlight">795</i>&nbsp;		}
<i class="no-highlight">796</i>&nbsp;	}
<i class="no-highlight">797</i>&nbsp;
<i class="no-highlight">798</i>&nbsp;	/**
<i class="no-highlight">799</i>&nbsp;	 * Removes the parent tree node reference link from the specified tree node
<i class="no-highlight">800</i>&nbsp;	 *
<i class="no-highlight">801</i>&nbsp;	 * @param node tree node to remove the parent tree node reference assignment from
<i class="no-highlight">802</i>&nbsp;	 * @param &lt;T&gt; type of the data store in the tree node
<i class="no-highlight">803</i>&nbsp;	 */
<i class="no-highlight">804</i>&nbsp;	protected static &lt;T&gt; void unlinkParent(TreeNode&lt;T&gt; node) {
<b class="fc"><i class="no-highlight">805</i>&nbsp;		node.parent = null;</b>
<i class="no-highlight">806</i>&nbsp;	}
<i class="no-highlight">807</i>&nbsp;
<i class="no-highlight">808</i>&nbsp;	/**
<i class="no-highlight">809</i>&nbsp;	 * Checks whether there is at least one not {@code null} element within
<i class="no-highlight">810</i>&nbsp;	 * the input collection
<i class="no-highlight">811</i>&nbsp;	 * &lt;pre&gt;
<i class="no-highlight">812</i>&nbsp;	 *     Validator.isAnyNotNull(Arrays.asList(&quot;foo&quot;, null))   = true
<i class="no-highlight">813</i>&nbsp;	 *     Validator.isAnyNotNull(null)                         = false
<i class="no-highlight">814</i>&nbsp;	 *     Validator.isAnyNotNull(Collections.emptyList())      = false
<i class="no-highlight">815</i>&nbsp;	 *     Validator.isAnyNotNull(Arrays.asList(null, null))    = false
<i class="no-highlight">816</i>&nbsp;	 * &lt;/pre&gt;
<i class="no-highlight">817</i>&nbsp;	 *
<i class="no-highlight">818</i>&nbsp;	 * @param collection input collection to check
<i class="no-highlight">819</i>&nbsp;	 * @param &lt;T&gt; type of the data, which parametrises collection
<i class="no-highlight">820</i>&nbsp;	 * @return {@code true} if there is at least one not {@code null} element within
<i class="no-highlight">821</i>&nbsp;	 *         the input collection; {@code false} otherwise
<i class="no-highlight">822</i>&nbsp;	 */
<i class="no-highlight">823</i>&nbsp;	protected static &lt;T&gt; boolean isAnyNotNull(Collection&lt;T&gt; collection) {
<b class="fc"><i class="no-highlight">824</i>&nbsp;		if (collection == null || collection.isEmpty()) {</b>
<b class="fc"><i class="no-highlight">825</i>&nbsp;			return false;</b>
<i class="no-highlight">826</i>&nbsp;		}
<b class="fc"><i class="no-highlight">827</i>&nbsp;		for (T item : collection) {</b>
<b class="fc"><i class="no-highlight">828</i>&nbsp;			if (item != null) {</b>
<b class="fc"><i class="no-highlight">829</i>&nbsp;				return true;</b>
<i class="no-highlight">830</i>&nbsp;			}
<b class="fc"><i class="no-highlight">831</i>&nbsp;		}</b>
<b class="fc"><i class="no-highlight">832</i>&nbsp;		return false;</b>
<i class="no-highlight">833</i>&nbsp;	}
<i class="no-highlight">834</i>&nbsp;
<i class="no-highlight">835</i>&nbsp;	/**
<i class="no-highlight">836</i>&nbsp;	 * Checks whether the specified collection is @{code null}, empty or if
<i class="no-highlight">837</i>&nbsp;	 * all of its elements are {@code null}
<i class="no-highlight">838</i>&nbsp;	 * &lt;pre&gt;
<i class="no-highlight">839</i>&nbsp;	 *     areAllNulls(null)                          = true
<i class="no-highlight">840</i>&nbsp;	 *     areAllNulls(Collections.emptyList())       = true
<i class="no-highlight">841</i>&nbsp;	 *     areAllNulls(Arrays.asList(null, null))     = true
<i class="no-highlight">842</i>&nbsp;	 *     areAllNulls(Arrays.asList(&quot;foo&quot;, null))    = false
<i class="no-highlight">843</i>&nbsp;	 * &lt;/pre&gt;
<i class="no-highlight">844</i>&nbsp;	 *
<i class="no-highlight">845</i>&nbsp;	 * @param collection input collection to check
<i class="no-highlight">846</i>&nbsp;	 * @param &lt;T&gt; type of the data, which parametrises collection
<i class="no-highlight">847</i>&nbsp;	 * @return {@code true} if the specified collection is {@code null}, empty
<i class="no-highlight">848</i>&nbsp;	 *         or if all of its elements are {@code null}; {@code false} otherwise
<i class="no-highlight">849</i>&nbsp;	 */
<i class="no-highlight">850</i>&nbsp;	protected static &lt;T&gt; boolean areAllNulls(Collection&lt;T&gt; collection) {
<b class="fc"><i class="no-highlight">851</i>&nbsp;		return !isAnyNotNull(collection);</b>
<i class="no-highlight">852</i>&nbsp;	}
<i class="no-highlight">853</i>&nbsp;
<i class="no-highlight">854</i>&nbsp;	/**
<i class="no-highlight">855</i>&nbsp;	 * Base tree node iterator, which is expected to be extended by {@link TreeNode}
<i class="no-highlight">856</i>&nbsp;	 * subclasses in order to perform custom implementation and return it in
<i class="no-highlight">857</i>&nbsp;	 * {@link #iterator()}
<i class="no-highlight">858</i>&nbsp;	 */
<b class="nc"><i class="no-highlight">859</i>&nbsp;	protected abstract class TreeNodeIterator implements Iterator&lt;TreeNode&lt;T&gt;&gt; {</b>
<i class="no-highlight">860</i>&nbsp;
<i class="no-highlight">861</i>&nbsp;		/**
<i class="no-highlight">862</i>&nbsp;		 * An expected size of the tree node required to check
<i class="no-highlight">863</i>&nbsp;		 * whether the tree node was changed during &lt;b&gt;foreach&lt;/b&gt;
<i class="no-highlight">864</i>&nbsp;		 * iteration
<i class="no-highlight">865</i>&nbsp;		 */
<b class="nc"><i class="no-highlight">866</i>&nbsp;		private long expectedSize = size();</b>
<i class="no-highlight">867</i>&nbsp;
<i class="no-highlight">868</i>&nbsp;		/**
<i class="no-highlight">869</i>&nbsp;		 * Reference to the current tree node within iteration
<i class="no-highlight">870</i>&nbsp;		 */
<i class="no-highlight">871</i>&nbsp;		private TreeNode&lt;T&gt; currentNode;
<i class="no-highlight">872</i>&nbsp;
<i class="no-highlight">873</i>&nbsp;		/**
<i class="no-highlight">874</i>&nbsp;		 * Reference to the next tree node within iteration
<i class="no-highlight">875</i>&nbsp;		 */
<b class="nc"><i class="no-highlight">876</i>&nbsp;		private TreeNode&lt;T&gt; nextNode = TreeNode.this;</b>
<i class="no-highlight">877</i>&nbsp;
<i class="no-highlight">878</i>&nbsp;		/**
<i class="no-highlight">879</i>&nbsp;		 * Indicates whether there is a next tree node available
<i class="no-highlight">880</i>&nbsp;		 * within iteration
<i class="no-highlight">881</i>&nbsp;		 */
<b class="nc"><i class="no-highlight">882</i>&nbsp;		private boolean nextNodeAvailable = true;</b>
<i class="no-highlight">883</i>&nbsp;
<i class="no-highlight">884</i>&nbsp;		/**
<i class="no-highlight">885</i>&nbsp;		 * Returns the leftmost node of the current tree node if the
<i class="no-highlight">886</i>&nbsp;		 * current tree node is not a leaf
<i class="no-highlight">887</i>&nbsp;		 *
<i class="no-highlight">888</i>&nbsp;		 * @return leftmost node of the current tree node if the current
<i class="no-highlight">889</i>&nbsp;		 *         tree node is not a leaf
<i class="no-highlight">890</i>&nbsp;		 * @throws TreeNodeException an exception that is thrown in case
<i class="no-highlight">891</i>&nbsp;		 *                           if the current tree node is a leaf
<i class="no-highlight">892</i>&nbsp;		 */
<i class="no-highlight">893</i>&nbsp;		protected abstract TreeNode&lt;T&gt; leftMostNode();
<i class="no-highlight">894</i>&nbsp;
<i class="no-highlight">895</i>&nbsp;		/**
<i class="no-highlight">896</i>&nbsp;		 * Returns the right sibling node of the current tree node if the
<i class="no-highlight">897</i>&nbsp;		 * current tree node is not root
<i class="no-highlight">898</i>&nbsp;		 *
<i class="no-highlight">899</i>&nbsp;		 * @return right sibling node of the current tree node if the current
<i class="no-highlight">900</i>&nbsp;		 *         tree node is not root
<i class="no-highlight">901</i>&nbsp;		 * @throws TreeNodeException an exception that may be thrown in case if
<i class="no-highlight">902</i>&nbsp;		 *                           the current tree node is root
<i class="no-highlight">903</i>&nbsp;		 */
<i class="no-highlight">904</i>&nbsp;		protected abstract TreeNode&lt;T&gt; rightSiblingNode();
<i class="no-highlight">905</i>&nbsp;
<i class="no-highlight">906</i>&nbsp;		/**
<i class="no-highlight">907</i>&nbsp;		 * Checks whether the current tree node is not a leaf and returns the
<i class="no-highlight">908</i>&nbsp;		 * leftmost node from {@link #leftMostNode()}
<i class="no-highlight">909</i>&nbsp;		 *
<i class="no-highlight">910</i>&nbsp;		 * @return leftmost node of the current tree node if the current tree
<i class="no-highlight">911</i>&nbsp;		 *         node is not a leaf
<i class="no-highlight">912</i>&nbsp;		 * @throws TreeNodeException an exception that is thrown in case
<i class="no-highlight">913</i>&nbsp;		 *                           if the current tree node is a leaf
<i class="no-highlight">914</i>&nbsp;		 */
<i class="no-highlight">915</i>&nbsp;		private TreeNode&lt;T&gt; checkAndGetLeftMostNode() {
<b class="nc"><i class="no-highlight">916</i>&nbsp;			if (isLeaf()) {</b>
<b class="nc"><i class="no-highlight">917</i>&nbsp;				throw new TreeNodeException(&quot;Leftmost node can&#39;t be obtained. Current tree node is a leaf&quot;);</b>
<i class="no-highlight">918</i>&nbsp;			} else {
<b class="nc"><i class="no-highlight">919</i>&nbsp;				return leftMostNode();</b>
<i class="no-highlight">920</i>&nbsp;			}
<i class="no-highlight">921</i>&nbsp;		}
<i class="no-highlight">922</i>&nbsp;
<i class="no-highlight">923</i>&nbsp;		/**
<i class="no-highlight">924</i>&nbsp;		 * Checks whether the current tree node is not root and returns the
<i class="no-highlight">925</i>&nbsp;		 * right sibling node from {@link #rightSiblingNode()}
<i class="no-highlight">926</i>&nbsp;		 *
<i class="no-highlight">927</i>&nbsp;		 * @return right sibling node of the current tree node if the current
<i class="no-highlight">928</i>&nbsp;		 *         tree node is not root
<i class="no-highlight">929</i>&nbsp;		 * @throws TreeNodeException an exception that may be thrown in case if
<i class="no-highlight">930</i>&nbsp;		 *                           the current tree node is root
<i class="no-highlight">931</i>&nbsp;		 */
<i class="no-highlight">932</i>&nbsp;		private TreeNode&lt;T&gt; checkAndGetRightSiblingNode() {
<b class="nc"><i class="no-highlight">933</i>&nbsp;			if (isRoot()) {</b>
<b class="nc"><i class="no-highlight">934</i>&nbsp;				throw new TreeNodeException(&quot;Right sibling node can&#39;t be obtained. Current tree node is root&quot;);</b>
<i class="no-highlight">935</i>&nbsp;			} else {
<b class="nc"><i class="no-highlight">936</i>&nbsp;				return rightSiblingNode();</b>
<i class="no-highlight">937</i>&nbsp;			}
<i class="no-highlight">938</i>&nbsp;		}
<i class="no-highlight">939</i>&nbsp;
<i class="no-highlight">940</i>&nbsp;		/**
<i class="no-highlight">941</i>&nbsp;		 * Returns {@code true} if the iteration has more elements;
<i class="no-highlight">942</i>&nbsp;		 * otherwise returns {@code false}
<i class="no-highlight">943</i>&nbsp;		 *
<i class="no-highlight">944</i>&nbsp;		 * @return {@code true} if the iteration has more elements;
<i class="no-highlight">945</i>&nbsp;		 *         {@code false} otherwise
<i class="no-highlight">946</i>&nbsp;		 */
<i class="no-highlight">947</i>&nbsp;		@Override
<i class="no-highlight">948</i>&nbsp;		public boolean hasNext() {
<b class="nc"><i class="no-highlight">949</i>&nbsp;			return nextNodeAvailable;</b>
<i class="no-highlight">950</i>&nbsp;		}
<i class="no-highlight">951</i>&nbsp;
<i class="no-highlight">952</i>&nbsp;		/**
<i class="no-highlight">953</i>&nbsp;		 * Returns the next element in the iteration
<i class="no-highlight">954</i>&nbsp;		 *
<i class="no-highlight">955</i>&nbsp;		 * @return the next element in the iteration
<i class="no-highlight">956</i>&nbsp;		 * @throws NoSuchElementException if the iteration has no more elements
<i class="no-highlight">957</i>&nbsp;		 */
<i class="no-highlight">958</i>&nbsp;		@Override
<i class="no-highlight">959</i>&nbsp;		public TreeNode&lt;T&gt; next() {
<b class="nc"><i class="no-highlight">960</i>&nbsp;			checkForConcurrentModification();</b>
<b class="nc"><i class="no-highlight">961</i>&nbsp;			if (!hasNext()) {</b>
<b class="nc"><i class="no-highlight">962</i>&nbsp;				throw new NoSuchElementException();</b>
<i class="no-highlight">963</i>&nbsp;			}
<b class="nc"><i class="no-highlight">964</i>&nbsp;			currentNode = nextNode;</b>
<b class="nc"><i class="no-highlight">965</i>&nbsp;			if (nextNode.isLeaf()) {</b>
<b class="nc"><i class="no-highlight">966</i>&nbsp;				if (nextNode.isRoot()) {</b>
<b class="nc"><i class="no-highlight">967</i>&nbsp;					nextNodeAvailable = false;</b>
<i class="no-highlight">968</i>&nbsp;				} else {
<i class="no-highlight">969</i>&nbsp;					do {
<b class="nc"><i class="no-highlight">970</i>&nbsp;						TreeNode&lt;T&gt; currentNode = nextNode;</b>
<b class="nc"><i class="no-highlight">971</i>&nbsp;						nextNode = nextNode.parent();</b>
<b class="nc"><i class="no-highlight">972</i>&nbsp;						if (currentNode.equals(TreeNode.this)) {</b>
<b class="nc"><i class="no-highlight">973</i>&nbsp;							nextNodeAvailable = false;</b>
<b class="nc"><i class="no-highlight">974</i>&nbsp;							break;</b>
<i class="no-highlight">975</i>&nbsp;						}
<b class="nc"><i class="no-highlight">976</i>&nbsp;						TreeNode&lt;T&gt; nextSibling = currentNode.iterator().checkAndGetRightSiblingNode();</b>
<b class="nc"><i class="no-highlight">977</i>&nbsp;						if (nextSibling != null) {</b>
<b class="nc"><i class="no-highlight">978</i>&nbsp;							nextNode = nextSibling;</b>
<b class="nc"><i class="no-highlight">979</i>&nbsp;							break;</b>
<i class="no-highlight">980</i>&nbsp;						}
<b class="nc"><i class="no-highlight">981</i>&nbsp;					} while (true);</b>
<i class="no-highlight">982</i>&nbsp;				}
<i class="no-highlight">983</i>&nbsp;			} else {
<b class="nc"><i class="no-highlight">984</i>&nbsp;				nextNode = nextNode.iterator().checkAndGetLeftMostNode();</b>
<i class="no-highlight">985</i>&nbsp;			}
<b class="nc"><i class="no-highlight">986</i>&nbsp;			return currentNode;</b>
<i class="no-highlight">987</i>&nbsp;		}
<i class="no-highlight">988</i>&nbsp;
<i class="no-highlight">989</i>&nbsp;		/**
<i class="no-highlight">990</i>&nbsp;		 * Checks whether tree node was changed during &lt;b&gt;foreach&lt;/b&gt;
<i class="no-highlight">991</i>&nbsp;		 * iteration and throws {@link ConcurrentModificationException}
<i class="no-highlight">992</i>&nbsp;		 * exception if so
<i class="no-highlight">993</i>&nbsp;		 */
<i class="no-highlight">994</i>&nbsp;		private void checkForConcurrentModification() {
<b class="nc"><i class="no-highlight">995</i>&nbsp;			if (expectedSize != size()) {</b>
<b class="nc"><i class="no-highlight">996</i>&nbsp;				throw new ConcurrentModificationException();</b>
<i class="no-highlight">997</i>&nbsp;			}
<i class="no-highlight">998</i>&nbsp;		}
<i class="no-highlight">999</i>&nbsp;
<i class="no-highlight">1000</i>&nbsp;		/**
<i class="no-highlight">1001</i>&nbsp;		 * Removes from the underlying tree the last element returned by this
<i class="no-highlight">1002</i>&nbsp;		 * iterator (optional operation)
<i class="no-highlight">1003</i>&nbsp;		 * &lt;p&gt;
<i class="no-highlight">1004</i>&nbsp;		 * This method can be called only once per call to {@link #next}.
<i class="no-highlight">1005</i>&nbsp;		 * The behavior of an iterator is unspecified if the underlying tree
<i class="no-highlight">1006</i>&nbsp;		 * is modified while the iteration is in progress in any way other
<i class="no-highlight">1007</i>&nbsp;		 * than by calling this method
<i class="no-highlight">1008</i>&nbsp;		 *
<i class="no-highlight">1009</i>&nbsp;		 * @throws IllegalStateException an exception that may be thrown in case
<i class="no-highlight">1010</i>&nbsp;		 *                               if remove was performed without any
<i class="no-highlight">1011</i>&nbsp;		 *                               iteration
<i class="no-highlight">1012</i>&nbsp;		 * @throws TreeNodeException an exception that may be thrown in case if
<i class="no-highlight">1013</i>&nbsp;		 *                           remove was performed on a root node
<i class="no-highlight">1014</i>&nbsp;		 */
<i class="no-highlight">1015</i>&nbsp;		@Override
<i class="no-highlight">1016</i>&nbsp;		public void remove() {
<b class="nc"><i class="no-highlight">1017</i>&nbsp;			String errorMessage = &quot;Failed to remove the tree node. &quot;;</b>
<b class="nc"><i class="no-highlight">1018</i>&nbsp;			if (!isIterationStarted()) {</b>
<b class="nc"><i class="no-highlight">1019</i>&nbsp;				throw new IllegalStateException(errorMessage + &quot;The iteration has not been performed yet&quot;);</b>
<i class="no-highlight">1020</i>&nbsp;			}
<b class="nc"><i class="no-highlight">1021</i>&nbsp;			if (currentNode.isRoot()) {</b>
<b class="nc"><i class="no-highlight">1022</i>&nbsp;				String message = String.format(errorMessage + &quot;The tree node %1$s is root&quot;, currentNode);</b>
<b class="nc"><i class="no-highlight">1023</i>&nbsp;				throw new TreeNodeException(message);</b>
<i class="no-highlight">1024</i>&nbsp;			}
<b class="nc"><i class="no-highlight">1025</i>&nbsp;			if (currentNode.equals(TreeNode.this)) {</b>
<b class="nc"><i class="no-highlight">1026</i>&nbsp;				throw new TreeNodeException(errorMessage + &quot;The starting node can&#39;t be removed&quot;);</b>
<i class="no-highlight">1027</i>&nbsp;			}
<b class="nc"><i class="no-highlight">1028</i>&nbsp;			checkForConcurrentModification();</b>
<b class="nc"><i class="no-highlight">1029</i>&nbsp;			TreeNode&lt;T&gt; currentNode = this.currentNode;</b>
<i class="no-highlight">1030</i>&nbsp;			while (true) {
<b class="nc"><i class="no-highlight">1031</i>&nbsp;				if (currentNode.isRoot()) {</b>
<b class="nc"><i class="no-highlight">1032</i>&nbsp;					nextNodeAvailable = false;</b>
<b class="nc"><i class="no-highlight">1033</i>&nbsp;					break;</b>
<i class="no-highlight">1034</i>&nbsp;				}
<b class="nc"><i class="no-highlight">1035</i>&nbsp;				TreeNode&lt;T&gt; rightSiblingNode = currentNode.iterator().checkAndGetRightSiblingNode();</b>
<b class="nc"><i class="no-highlight">1036</i>&nbsp;				if (rightSiblingNode != null) {</b>
<b class="nc"><i class="no-highlight">1037</i>&nbsp;					nextNode = rightSiblingNode;</b>
<b class="nc"><i class="no-highlight">1038</i>&nbsp;					break;</b>
<i class="no-highlight">1039</i>&nbsp;				}
<b class="nc"><i class="no-highlight">1040</i>&nbsp;				currentNode = currentNode.parent;</b>
<b class="nc"><i class="no-highlight">1041</i>&nbsp;			}</b>
<b class="nc"><i class="no-highlight">1042</i>&nbsp;			TreeNode&lt;T&gt; parent = this.currentNode.parent();</b>
<b class="nc"><i class="no-highlight">1043</i>&nbsp;			parent.dropSubtree(this.currentNode);</b>
<b class="nc"><i class="no-highlight">1044</i>&nbsp;			this.currentNode = parent;</b>
<b class="nc"><i class="no-highlight">1045</i>&nbsp;			expectedSize = size();</b>
<i class="no-highlight">1046</i>&nbsp;		}
<i class="no-highlight">1047</i>&nbsp;
<i class="no-highlight">1048</i>&nbsp;		/**
<i class="no-highlight">1049</i>&nbsp;		 * Returns whether iteration has been started
<i class="no-highlight">1050</i>&nbsp;		 *
<i class="no-highlight">1051</i>&nbsp;		 * @return {@code true} if iteration has been started; {@code false} otherwise
<i class="no-highlight">1052</i>&nbsp;		 */
<i class="no-highlight">1053</i>&nbsp;		private boolean isIterationStarted() {
<b class="nc"><i class="no-highlight">1054</i>&nbsp;			return currentNode != null;</b>
<i class="no-highlight">1055</i>&nbsp;		}
<i class="no-highlight">1056</i>&nbsp;
<i class="no-highlight">1057</i>&nbsp;	}
<i class="no-highlight">1058</i>&nbsp;
<i class="no-highlight">1059</i>&nbsp;}
</div>
</pre>
</div>

<script type="text/javascript">
(function() {
    var msie = false, msie9 = false;
    /*@cc_on
      msie = true;
      @if (@_jscript_version >= 9)
        msie9 = true;
      @end
    @*/

    if (!msie || msie && msie9) {
        var codeBlock = document.getElementById('sourceCode');

        if (codeBlock) {
            hljs.highlightBlock(codeBlock);
        }
    }
})();
</script>

<div class="footer">
    
    <div style="float:right;">generated on 2021-12-13 00:09</div>
</div>
</body>
</html>
